package top.minuy.subject.leetcode._208;
/**
 * @author Minuy
 * @time 22:34
 * @date 2021/10/27
 */
public class Trie {

    /**
     * 映射
     * @param <K>
     * @param <V>
     */
    interface map<K, V> {
        /**
         * 向字典中添加键值对
         *
         * @param key 键
         * @param val 值
         */
        void add(K key, V val);

        /**
         * 删除一个键值对
         *
         * @param key 要被删除的键
         * @return 返回被删除键的值，如若键不存在，返回空
         */
        V remove(K key);

        /**
         * 查询键是否存在
         *
         * @param key 要查询的键
         * @return 此键是否存在
         */
        boolean contains(K key);

        /**
         * 获取一个键的值
         *
         * @param key 键
         * @return 值
         */
        V get(K key);

        /**
         * 修改一个键值对
         *
         * @param key 键
         * @param newVal 值
         */
        void set(K key, V newVal);

        /**
         * 获取字典的大小
         *
         * @return 字典的大小
         */
        int getSize();

        /**
         * 判断字典是否为空
         *
         * @return 字典是否为空
         */
        boolean isEmpty();
    }

    /**
     * 二分搜索树实现的字典
     * @param <K>
     * @param <V>
     */
    class BSTMap<K extends Comparable<K>,V> implements map<K,V> {

        class Node{
            // 键
            public K key;
            // 值
            public V val;
            // 右子树
            public Node right;
            // 左子树
            public Node left;

            /**
             * 初始化一个节点
             * @param key 节点的键
             * @param val 节点的值
             */
            public Node(K key,V val){
                this.key = key;
                this.val = val;
            }
        }

        /**
         * 根节点
         */
        Node root;
        /**
         * 大小
         */
        int size;

        public BSTMap(){
            root = null;
            size = 0;
        }

        /**
         * 根据key获取节点
         * @param root 根节点
         * @param key 要查找的key
         * @return 对应的节点或者null
         */
        private Node getNode(Node root,K key){
            if(root==null){
                return null;
            }

            if(root.key.compareTo(key)>0){
                return getNode(root.left,key);
            }else if (root.key.compareTo(key)<0){
                return getNode(root.right,key);
            }else { // root.key.compareTo(key) == 0
                return root;
            }
        }

        /**
         * 向字典中添加键值对
         *
         * @param key 键
         * @param val 值
         */
        @Override
        public void add(K key, V val) {
            root = add(root,key,val);
        }

        public Node add(Node node,K key, V val) {
            if (node == null){
                size++;
                return new Node(key,val);
            }

            if(key.compareTo(node.key)<0){
                node.left = add(node.left,key,val);
            }else if(key.compareTo(node.key)>0){
                node.right = add(node.right,key,val);
            }else {  // key.compareTo(node.key) == 0
                node.val = val;
            }

            return node;
        }

        /**
         * 获取这棵树中的最小值
         * @param node 根节点
         * @return 最小值所在的节点
         */
        private Node getMinimum(Node node){
            if (node == null){
                return null;
            }
            if(node.left ==null){
                return node;
            }else {
                return getMinimum(node.left);
            }
        }

        private Node removeMinimum(Node node){
            if(node == null){
                return null;
            }

            if (node.left == null){
                Node t = node.right;
                node.right = null;
                size--;
                return t;
            }else{
                node.left = removeMinimum(node.left);
            }
            return node;
        }

        /**
         * 删除一个键值对
         *
         * @param key 要被删除的键
         * @return 返回被删除键的值，如若键不存在，返回空
         */
        @Override
        public V remove(K key) {
            Node node = getNode(root,key);
            if (node==null){
                return null;
            }else {
                root = remove(root,key);
                return node.val;
            }
        }

        private Node remove(Node node,K key){
            if(node == null){
                return null;
            }
            if(node.key.compareTo(key)>0){
                return remove(node.left,key);
            }else if(node.key.compareTo(key)<0){
                return remove(node.right,key);
            }else { // node.key.compareTo(key) == 0
                if(node.left == null){
                    Node t = node.right;
                    node.right = null;
                    size--;
                    return t;
                }

                if(node.right == null){
                    Node t = node.left;
                    node.left = null;
                    size--;
                    return t;
                }

                Node minimumNode = getMinimum(node);
                node.right = removeMinimum(node.right);

                minimumNode.left = node.left;
                minimumNode.right = node.right;

                node.right = node.left = null;

                return minimumNode;
            }
        }

        /**
         * 查询键是否存在
         *
         * @param key 要查询的键
         * @return 此键是否存在
         */
        @Override
        public boolean contains(K key) {
            return getNode(root,key)!=null;
        }

        /**
         * 获取一个键的值
         *
         * @param key 键
         * @return 值
         */
        @Override
        public V get(K key) {
            // 当根节点为空的时候返回空，而不是空指针异常
            return getNode(root,key)==null?null:getNode(root,key).val;
        }

        /**
         * 修改一个键值对
         *
         * @param key    键
         * @param newVal 值
         */
        @Override
        public void set(K key, V newVal) {
            Node node = getNode(root,key);
            if(node==null){
                throw new IllegalArgumentException("Set failed. The \""+key.toString()+"\" is not exists.");
            }else {
                node.val = newVal;
            }
        }

        /**
         * 获取字典的大小
         *
         * @return 字典的大小
         */
        @Override
        public int getSize() {
            return size;
        }

        /**
         * 判断字典是否为空
         *
         * @return 字典是否为空
         */
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    }


    // 节点
    class Node{
        // 是不是单词末尾
        boolean isWord;
        // 子节点
        BSTMap<Character, Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new BSTMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie(){
        size = 0;
        root = new Node();
    }


    public void insert(String word) {
        Node cur = root;
        for (int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if (cur.next.get(c) == null){
                cur.next.add(c,new Node());
            }
            // 这里不能把cur.next.get(c)的值缓存起来，因为为空时会新建，这里只能获取最新值
            cur = cur.next.get(c);
        }
        if(!cur.isWord) {
            cur.isWord = true;
            size++;
        }
    }

    public boolean search(String word) {
        Node cur = root, temp;
        for (int i=0;i<word.length();i++){
            char c = word.charAt(i);
            // 这边没有涉及修改操作，可以使用缓存
            temp = cur.next.get(c);
            if (temp == null){
                return false;
            }
            // 要更改游标
            cur = temp;
        }
        return cur.isWord;
    }

    public boolean startsWith(String prefix) {
        Node cur = root,temp;
        for (int i=0;i<prefix.length();i++){
            temp = cur.next.get(prefix.charAt(i));
            if(temp==null){
                return false;
            }
            cur = temp;
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
